package PAT;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class TNode{
    int ad;
    int value;
    int next;


    public TNode(int ad, int value, int next) {
        this.ad = ad;
        this.value = value;
        this.next = next;
    }
}

public class PAT1074 {
    public static void main(String[] args) {
        TNode[] tNodes = new TNode[100001];
        Scanner scanner = new Scanner(System.in);
        int start = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int ad = scanner.nextInt();
            TNode tNode = new TNode(ad, scanner.nextInt(), scanner.nextInt());
            tNodes[ad] = tNode;
        }
        List<Integer> ans = new ArrayList<>();
        for (int id = start; id !=-1 ; id = tNodes[id].next) {
            ans.add(id);
        }
        for (int i = 0; i+k-1 < n; i+=k-1) {
            reverse(ans,i,i+k-1);
        }
        for (int i = 0; i < n - 1; i++) {
            System.out.printf("%05d %d %05d\n",ans.get(i),tNodes[ans.get(i)].value,ans.get(i+1));
        }
        System.out.printf("%05d %d -1",ans.get(n-1),tNodes[ans.get(n-1)].value);

//        int i = k-1;
//        for (; i < n; i+=k-1) {
//            for (int j = i; j > i-k  ; j--) {
//                System.out.printf("%05d", ans.get(j));
//                System.out.print(" ");
//                System.out.print(tNodes[ans.get(j)].value+" ");
//                if(i==n-1){
//                    System.out.print(-1);
//                }else if(j!=i-k+1){
//                    System.out.printf("%05d",ans.get(j-1));
//                }else {
//                    System.out.printf("%05d",ans.get(i+1));
//                }
//                System.out.println("");
//            }
//        }
//        for (int j = i -k+2; j < n; j++) {
//            if(tNodes[ans.get(j)].next==-1) {
//                System.out.printf("%05d %d %d\n",ans.get(j),tNodes[ans.get(j)].value,tNodes[ans.get(j)].next);
//            }else{
//                System.out.printf("%05d %d %05d\n",ans.get(j),tNodes[ans.get(j)].value,tNodes[ans.get(j)].next);
//            }
//        }
    }

    private static void reverse(List<Integer> ans, int i, int j) {
        while (i<j){
            Integer p = ans.get(i);
            ans.set(i,ans.get(j));
            ans.set(j,p);
            i++;
            j--;
        }
    }
}
